/*
 *https://leetcode.cn/problems/most-stones-removed-with-same-row-or-column/
 *947. 移除最多的同行或同列石头
 *并查集
*/

class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        // 定义一个队列用于广度优先搜索
        queue<pair<int, int>> q;
        
        // 定义一个布尔数组 visited 用于记录哪些石头已经被访问过
        bool visited[stones.size()];
        memset(visited, false, sizeof(visited));
        
        // 记录连通分量的数量
        int count = 0;
        
        // 遍历所有的石头
        for (int i = 0; i < stones.size(); i++) {
            if (visited[i] == true)
                continue;  // 如果当前石头已经被访问过，则跳过
            
            count++;  // 每次找到一个新的连通分量，计数加 1
            
            // 将当前石头加入队列，开始广度优先搜索
            q.push(make_pair(stones[i][0], stones[i][1]));
            visited[i] = true;
            
            // 广度优先搜索
            while (!q.empty()) {
                int m = q.front().first;  // 当前石头的行坐标
                int n = q.front().second;  // 当前石头的列坐标
                q.pop();
                
                // 遍历所有石头，检查是否有同行的石头
                for (int j = 0; j < stones.size(); j++) {
                    if (visited[j] == false && stones[j][0] == m) {
                        visited[j] = true;
                        q.push(make_pair(stones[j][0], stones[j][1]));  // 将同行的石头加入队列
                    }
                }
                
                // 遍历所有石头，检查是否有同列的石头
                for (int j = 0; j < stones.size(); j++) {
                    if (visited[j] == false && stones[j][1] == n) {
                        visited[j] = true;
                        q.push(make_pair(stones[j][0], stones[j][1]));  // 将同列的石头加入队列
                    }
                }
            }
        }
        
        // 返回可以移除的最大石头数量
        return stones.size() - count;
    }
};
